//优美的排列
https://leetcode.cn/problems/beautiful-arrangement/description/

class Solution {
public:
    int ret = 0;
    bool arr[16] = {false};
    int _n = 0;

    int countArrangement(int n) 
    {
        _n = n;
        dfs(1);
        return ret;
    }

    void dfs(int level)
    {
        if(level == _n + 1)
        {
            ret++;
            return;
        }

        for(int i = 1; i <= _n; i++)
        {
            if(!arr[i])
            {
                if(i % level == 0 || level % i == 0)
                { //可以走递归
                    arr[i] = true;
                    dfs(level + 1);
                    arr[i] = false;
                }
            }  
        }
    }
};